//
// Created by Jisam on 2024/5/29.
//
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define endl "\n"
#define x first
#define y second
#define INF 0x3f3f3f3f
#define PII pair<int,int>
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int x[20], n, k;
vector<bool> isPrime;

vector<bool> get_is_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return is_prime;
}

int res;

void dfs(int now, int l, int sum) {
    if (now == k) {
        if (isPrime[sum]) { res++;
//            cout << "{ " << sum <<" "<< isPrime[sum]<< " }";
        }
    }
    for(int i = l ; i < n;i++){
        dfs( now +1 , i + 1,sum +x[i]);
    }
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x, x + n);
    isPrime = get_is_primes(x[n - 1] * 5);

    dfs(0, 0, 0);
    cout << res;

    return 0;
}